package com.liuyfly.leetcode.questions;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

import com.liuyfly.leetcode.model.TreeNode;
import com.liuyfly.leetcode.util.LeetcodeUtil;

import com.liuyfly.leetcode.util.TreeNodeUtil;
import lombok.extern.slf4j.Slf4j;

/**
 * @author liuyangfang at 2022-10-19 10:49
 */
@Slf4j
public class Question0094 {
    /**
     * 给定一个二叉树的根节点 root ，返回它的 中序 遍历 。 <br/>
     * <br/>
     * 递归
     * <br/>
     * 链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
     */
    public static List<Integer> inorderTraversalRecursive(TreeNode<Integer> root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }

    public static void inorder(TreeNode<Integer> node, List<Integer> list) {
        if (node == null) {
            return;
        }
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }

    /**
     * 迭代
     */
    public static List<Integer> inorderTraversal(TreeNode<Integer> root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode<Integer>> deque = new LinkedList<>();
        return result;
    }

    public static void main(String[] args) {
        TreeNode<Integer> root = LeetcodeUtil.initTreeNode(true);
        List<Integer> result = inorderTraversalRecursive(root);
        LeetcodeUtil.printList(result);

        result = TreeNodeUtil.preorderTraversal(root);
        LeetcodeUtil.printList(result);
        result = TreeNodeUtil.inorderTraversal(root);
        LeetcodeUtil.printList(result);
        result = TreeNodeUtil.postorderTraversal(root);
        LeetcodeUtil.printList(result);
    }
}
